/*	Program P12-2 Insert vertex.

    Brooks/Cole Publishing Company
	An International Thomson Publishing Company
	Copyright 1998. All Rights Reserved
*/

/*	==================== insertVertex ==================== 
	This function inserts new data into the graph.
	   Pre    dataIn contains data to be inserted
	   Post   data have been inserted or memory overflow
	   Return +1 if successful; -1 if memory overflow
*/

/*	==================== insertVertex ==================== 
	This function inserts new data into the graph.
	   Pre    dataIn contains data to be inserted
	   Post   data have been inserted or memory overflow
	   Return +1 if successful; -1 if memory overflow
*/

template <class TYPE, class KTYPE> 
int Graph<TYPE, KTYPE> ::  insertVertex (TYPE dataIn) 
{
//	Local Definitions 
	Vertex<TYPE>  *newPtr;
	Vertex<TYPE>  *locPtr;
	Vertex<TYPE>  *predPtr;
	
//	Statements 
	newPtr = new Vertex<TYPE>;
	if (newPtr)
	   {
	    newPtr->pNextVertex  = NULL;
	    newPtr->data         = dataIn;
	    newPtr->inDegree     = 0;
	    newPtr->outDegree    = 0;
	    newPtr->processed    = 0;
	    newPtr->pArc         = NULL;
	    count ++;
	   } // if new
	else
	    // Memory overflow 
	    return -1;
	//  Now find insertion point 
	locPtr = first;
	if (!locPtr)
	// Empty graph. Insert at beginning. 
	   first = newPtr;
	else
	   {
	    predPtr = NULL;
	    while (locPtr && dataIn.key > (locPtr->data).key)
	       {
	        predPtr = locPtr;
	        locPtr  = locPtr->pNextVertex;
	       } //  while 
	    if (!predPtr)
	       //  Insert before first vertex 
	       first = newPtr;
	    else
	       predPtr->pNextVertex = newPtr;
	    newPtr->pNextVertex = locPtr;
	   } // else
	return 1;
}	// insertVertex   
